The Alternating Direction Method of Multipliers (ADMM), which is a variant of an augmented Lagrangian scheme, uses partial updates for dual variables to solve a quadratic program. The ADMM alternately solves for a first variable while holding a second variable fixed, and solving for the second variable while holding the first variable fixed, see Boyd et al. “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Foundations and Trends in Machine Learning, vol. 3, no. 1, p. 1-122, 2011. Rather than iterating until convergence as in the Lagrangian-augmented problem, which is possibly complex, the ADMM performs iterations of alternating steps of updates on subsets of the variables.
The ADMM is frequently used for solving structured convex quadratic programs (QP) in applications, such as for example, compressive sensing, image processing, machine learning, distributed optimization, regularized estimation, semi-definite programming, and real-time control and signal processing applications, to name but a few.
Of particular interest to the invention is the application of ADMM to model predictive control (MPC) problems for application to systems with uncertain parameters. MPC is a method for controlling constrained dynamical systems, such as robots, automotive vehicles, spacecrafts, HVAC systems, processing machines, by repeatedly solving a finite horizon optimal control formulated from a mathematical model of the system dynamics, constraints, and a user specified cost function. Uncertainty arises due to the presence of disturbances that affect the system dynamics or due to mismatch between the model of the system dynamics and the true system dynamics. When probability information can be associated to the uncertain values, a stochastic system is obtained.
For linear models of the systems with a quadratic cost function and subject to linear constraints, the MPC finite horizon optimal control problem can be formulated as a parametric QP. At every control cycle, a specific QP is generated from the parametric quadratic program and the current values of the system state, and possibly the current reference. Then, the QP is solved, and the first part of the control input sequence is applied as control input. At the following control cycle, a new optimization problem is solved from the updated system state. MPC has been increasingly applied to systems with fast dynamics where the MPC is implemented in a low computational power embedded processors.
U.S. Pat. No. 8,600,525 discloses an active set algorithm that can be used for solving MPC generated QP problems. U.S. Pat. No. 7,328,074 discloses a method of providing an active-set algorithm wherein an initial guess for an optimization problem is provided from the solution of a previous optimization. U.S. Publication 20060282177 discloses an interior point algorithm for solving quadratic programs that arise in the context of model predictive control of gas turbine engines.
However, the computational effort per iteration of those methods can be prohibitive for application to large scale problems. The complexity of the operations that are performed, such as the solution of large scale linear systems, makes them infeasible for the type of computing hardware commonly used in real-time control and signal processing applications.
Methods such as gradient methods and accelerated gradient methods cannot easily handle linear inequality constraints. Low complexity fast optimization methods have been developed for MPC. U.S. Publication 20120281929 discloses a method for solving quadratic programs with non-negative constraints and a method to optimize such method for application to MPC.
A fast gradient algorithm is described for an application to MPC by Richter et al., “Computational Complexity Certification for Real-Time MPC With Input Constraints Based on the Fast Gradient Method,” IEEE Trans. Automat. Contr. 57(6): 1391-1403, 2012.
A Lagrangian method for MPC is described by Kögel et al., “Fast predictive control of linear, time-invariant systems using an algorithm based on the fast gradient method and augmented Lagrange multipliers,” CCA 2011: 780-785, 2011.
However, those methods are limited in the application by the types of constraints that can be handled, e.g., Richter et al., or can only handle input constraints, or need to perform division operations, e.g., in U.S. Publication 20120281929, which are time consuming in the computing hardware for MPC, or by complex iteration, e.g., Kögel et al. This is mainly due to the need of achieving the solution of the Lagrangian-augmented problem, which is complex due to the presence of constraints, before updating the Lagrange multipliers, multipliers at every update.
Thus, there is a need to provide a method that can solve large scale problems with small computational complexity per iteration, rapid convergence when problems are feasible, and quick detection of infeasibility.